Rivest-Shamir-Adleman (RSA) public-key cryptography has been widely used in various secure communication protocols, such as Secure Sockets Layer (SSL) and Transport Layer Security (TLS). Public-key certificates defined in the X.509 standard are also employed to verify the identities of people, documents, organizations, and/or devices. Typically, a world-wide network of Public-key Certificate Authorities creates X.509 certificates and digitally signs these certificates to attest to these digital identities.
The security of public-key cryptography is usually based on the impracticality of solving certain mathematical problems using currently available computing powers. For example, RSA public-key cryptography is based on the difficulty of factoring very large integers. Other public-key systems, such as the Diffie-Hellman key-agreement protocol or the Digital Signature Algorithm, are based on mathematical problems like computing discrete logarithms.
The emergence of quantum computing, however, threatens the security of public-key cryptography due to its unprecedented computing power. For example, it is believed that integer factorization can be efficiently solved by a quantum computer using Shor's algorithm to find the factors of the integer, thereby threatening to break all RSA public-key cryptographic systems. These systems are currently used to protect secure Web pages, emails, and many other types of data, and their security can have significant implications for almost everyone.
Although quantum resistant public-key crypto-systems are being developed, none has been shown to be practical for widespread use, so far. Thus, a need exists for methods and apparatus for network communications that are resistant to attacks or encryption by quantum computers.